#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void dfs(Tree *root, Tree *&head)
{
    if (!root) return;
    if (root->right) 
	dfs(root->right, head);
    if (head) head->left = root;
    root->right = head;
    head = root;
    dfs(root->left, head);
}

Tree *treeToList(Tree *root)
{
    Tree *head = NULL;
    dfs(root, head);
    Tree *cur = head;
    Tree *pre;
    while (cur) {
	cout << cur-> data << " ";
	pre = cur;
	cur = cur->right;
    }
    cur = pre;
    cout << endl;
    while (cur) {
	cout << cur-> data << " ";
	pre = cur;
	cur = cur->left;
    }
    return head;
}


int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,11,35,56};
    int input2[] = {6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);
    treeToList(root);
}
